/**
 * Created by CJJ on 2017/9/25.
 *
 */
val `$` = Int.MAX_VALUE
val N = 6
val graph = arrayOf(
        arrayOf(0, 1, 12, `$`, `$`, `$`),
        arrayOf(`$`, 0, 9, 3, `$`, `$`),
        arrayOf(`$`, `$`, 0, `$`, 5, `$`),
        arrayOf(`$`, `$`, 4, 0, 13, 15),
        arrayOf(`$`, `$`, `$`, `$`, 0, 4),
        arrayOf(`$`, `$`, `$`, `$`, `$`, 0)
)


fun main(args: Array<String>) {

    val dist = arrayOf(0, 1, 12, `$`, `$`, `$`)
    val path = arrayOf(0, 0, 0, 0, 0, 0)
    val s = ArrayList<Int>()
    s.add(0)
    //初始化dist


    for (index in 0 until N) {

        var u: Int = 0
        for (j in 0 until N)
        //如果这个点还没有检测过，并且是与起始点是可到达的
            if (!s.contains(j) && dist[j] < `$`) {
                u = j
            }
        s.add(u)

        for (k in 0 until N) {
            if (graph[u][k] < `$` && graph[u][k] + dist[u] < dist[k]) {
                dist[k] = graph[u][k] + dist[u]
                path[k] = u
            }
        }
        path.forEach { print("$it  ") }
        println("")

//        (0..N - 1)
//                .filter { graph[u][it] < `$` && graph[u][it] + dist[u] < dist[it] }
//                .forEach {
//                    dist[it] = graph[u][it] + dist[u]
//                    path[it] = u
//                }
    }


//use list

    var index = Node(null, null)
    val header: Node? = index
    for (a in 1..N - 2) {
        val next = Node(null, null)
        index.next = next
        next.prev = index
        index = next
    }

    var item = header
    while (item != null) {
        print("${item.value}  ")
        item = item.next
    }
}

class Node {

    var prev: Node?
    var next: Node?
    var value: Boolean = false


    constructor(prev: Node?, next: Node?, value: Boolean) {
        this.prev = prev
        this.next = next
        this.value = value
    }

    constructor(prev: Node?, next: Node?) {
        this.prev = prev
        this.next = next
    }
}